package Leetcode;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水。
 */
public class 力扣42_接雨水 {
    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5}));
    }

    // 暴力法 每一个柱子上边能够承载多少格水 取决于左边最大柱子和右边最大柱子的最小值 减去当前柱子高度
    // 时间复杂度： O(n^2) 数组中的每个元素都需要向左向右扫描。
    static int trap(int[] height) {
        int result = 0;
        int length = height.length;
        // 依次计算每根柱子上的水
        for (int i = 0; i < length; i++) {
            int leftMax = 0, rightMax = 0;

            // 寻找柱子左边的最高值
            for (int j = i; j >= 0; j--) {
                leftMax = Math.max(leftMax, height[j]);
            }

            // 寻找柱子右边的最高值
            for (int j = i; j < length; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }

            // 当前柱子能够盛水 左右柱子的最低值 - 当前柱子的高度
            result += Math.min(leftMax, rightMax) - height[i];
        }
        return result;
    }

    // 动态法 由上边的解法 想到提前存储左右边柱子的最大值
    // 从左往右去寻求阴影 得到左边最大值
    // 从右往左去寻求阴影 得到右边最大值
    // 时间复杂度：O(n)   存储最大高度数组 需要两次遍历 每次 O(n)   最终使用存储的数据更新ans O(n)
    static int trap1(int[] height) {
        int length = height.length;

        int[] dpLeft = new int[length];
        int[] dpRight = new int[length];

        int leftMax = 0, rightMax = 0;
        for (int i = 0; i < length; i++) {
            dpLeft[i] = leftMax = Math.max(leftMax, height[i]);
        }
        for (int i = length - 1; i >= 0; i--) {
            dpRight[i] = rightMax = Math.max(rightMax, height[i]);
        }

        int res = 0;
        for (int i = 0; i < length; i++) {
            res += Math.min(dpLeft[i], dpRight[i]) - height[i];
        }
        return res;
    }

}
